package netflow;
import java.util.*;
/*
 * Ford-Fulkerson algorithm to calculate maximum flow in the network
 * @author rashmi
 */
public class FF {
	private HashMap<Edge, Double> edgeFlow = new HashMap<Edge, Double>();
	//private static Map<Edge, Double> edgeResidualMap;
    private double maxvalue = 0.0;  // current value of max flow  
    private Vertex s;
    private Vertex t;
    private SimpleGraph SG;
    
    public FF(SimpleGraph SG, Vertex s, Vertex t)
    {
    	this.s = s;
    	this.t= t;
    	this.SG = SG;
    	calculateMaxFlow();
    }
    
    private void calculateMaxFlow()
    {
    	maxvalue = 0.0;
    	
    	// Initialize residualCapacity in edges to max capacity
    	// Create new edges for reverse direction with capacity 0
    	Iterator eI;
    	ArrayList<Edge> backwardEdges = new ArrayList<Edge>();
		for (eI = SG.edges(); eI.hasNext();) {
			Edge e1 = (Edge) eI.next();
			Edge backwardEdge = new Edge(e1.getSecondEndpoint(), e1.getFirstEndpoint(), new Double(0.0), "backwardEdge");
			backwardEdges.add(backwardEdge);
			edgeFlow.put(e1, new Double(0.0));			
		}
		for(Edge e:backwardEdges)
		{
			Edge newEdge = SG.insertEdge(e.getFirstEndpoint(), e.getSecondEndpoint(), new Double(0.0), "backwardEdge");
			edgeFlow.put(newEdge, new Double(0.0));
		}
		backwardEdges.clear();
		backwardEdges = null;
		
		path.clear();
		edgeVisited.clear();
		while (hasPath(s, t)) {
			maxvalue += augmentFlow(SG, path);
			
			path.clear();
			edgeVisited.clear();
			
		}
    	
		System.out.println("MaxFlow: "+maxvalue);
    	
    }
    
    private double augmentFlow(SimpleGraph SG, ArrayList<Edge> path) {
    	// Calculate minimum flow possible
    	double minCapacity = Double.POSITIVE_INFINITY;
    	for(Edge e1 : path) {
    		minCapacity = ((Double)e1.getData()).doubleValue() < minCapacity ? ((Double)e1.getData()).doubleValue():minCapacity; 
    	}
    	
    	for (Edge uvEdge: path) {
    		if (uvEdge.getName() == null)
    		{
    			// Forward edge
    			double newFlow = edgeFlow.get(uvEdge).doubleValue() + minCapacity;
    			edgeFlow.put(uvEdge, newFlow);
    			
    			// decrease capacity in this edge;
    			double residualCapacity = ((Double)uvEdge.getData()).doubleValue() - minCapacity;
    			uvEdge.setData(new Double(residualCapacity));
    			Edge vuEdge = findEdge(uvEdge.getSecondEndpoint(), uvEdge.getFirstEndpoint());
    			
    			// Increase capacity on the backward edge
    			residualCapacity = ((Double)vuEdge.getData()).doubleValue() + minCapacity;
    			vuEdge.setData(new Double(residualCapacity));
    			
    		}
    		else {
    			// This is backward edge. 
    			// Decrease flow in the corresponding forward edge (v,u)
    			Edge vuEdge = findEdge(uvEdge.getSecondEndpoint(), uvEdge.getFirstEndpoint());
    			double newFlow = edgeFlow.get(vuEdge).doubleValue() - minCapacity;
    			edgeFlow.put(uvEdge, newFlow);
    			
    			// decrease capacity in this edge;
    			double residualCapacity = ((Double)uvEdge.getData()).doubleValue() - minCapacity;
    			uvEdge.setData(new Double(residualCapacity));
    			
    			// Increase capacity on the forward edge
    			residualCapacity = ((Double)vuEdge.getData()).doubleValue() + minCapacity;
    			vuEdge.setData(new Double(residualCapacity));    			
    		}
    	}
    	return minCapacity;
    }
    
    private Edge findEdge(Vertex v1, Vertex v2) {
    	Iterator eI;
    	for (eI = SG.edges(); eI.hasNext();) {
			Edge e1 = (Edge) eI.next();
			if (e1.getFirstEndpoint().equals(v1) && e1.getSecondEndpoint().equals(v2)) {
				return e1;
			}
		}
    	return null;
    }
    
    HashMap<Edge, Boolean> edgeVisited = new HashMap<Edge, Boolean>();
    HashMap<Vertex, Boolean> vertexFinished = new HashMap<Vertex, Boolean>();
    ArrayList<Edge> path = new ArrayList<Edge>(); 
	
    private boolean hasPath(Vertex source, Vertex dest) {
    	if (source.equals(dest))
    		return true;
    	if (vertexFinished.containsKey(source))
    		return false;
    	Iterator<Edge> sourceEdges = source.incidentEdgeList.iterator();
    	for (; sourceEdges.hasNext();) {
			Edge e1 = (Edge) sourceEdges.next();
			if(e1.getFirstEndpoint().equals(source)) {
				// Consider only edges that start from here.
				if (!edgeVisited.containsKey(e1))
				{
					// mark as visited
					edgeVisited.put(e1, Boolean.TRUE);
					if (((Double)e1.getData()).doubleValue() > 0.0)
					{
						if (hasPath(e1.getSecondEndpoint(), dest))
						{
							// Destination found in this path.. Add this edge to the path
							path.add(e1);
							return true;
						}
					}
					
				}
			}
		}
    	vertexFinished.put(source, Boolean.TRUE);
    	return false;
    	
    }
    
    public static void main(String args[]) {
		SimpleGraph SG = new SimpleGraph();
		GraphInput.LoadSimpleGraph(SG, "g1.txt");

		Iterator i;
		Vertex v;
		Edge e;
		System.out.println("Iterating through vertices...");
		for (i = SG.vertices(); i.hasNext();) {
			v = (Vertex) i.next();
			System.out.println("found vertex " + v.getName());
			Iterator j;
			for (j = SG.incidentEdges(v); j.hasNext();) {
				e = (Edge) j.next();
				System.out.println("  found edge " + e.getData());
			}
		}

		Iterator eI;
		for (eI = SG.edges(); eI.hasNext();) {
			Edge e1 = (Edge) eI.next();
			// System.out.println(e1.getData());
		}

		try {
			new FF(SG, (Vertex) SG.vertexList.getFirst(), (Vertex) SG.vertexList.getLast());
		} catch (Exception e1) {
			e1.printStackTrace();
		}

	}
}